# 在什么样的情况下贪心策略得到的结果就是全局最优解
# 贪心策略适用的问题需要满足以下两个条件
# 贪心选择性质: 每次选择局部最优，而且每次选择以后就不能再修改了
# 最优子结构：一个问题的最优解包含其子问题的最优解

# 使用贪心策略求解教室排课问题，使得该教师所上的课最多，下面算法的时间复杂度未O(nlogn)


def schedule(course):
    sorted_courses = sorted(course, key=lambda s: s['end'])  # 按结束时间进行排序
    result = [sorted_courses[0]]  # 将第一个查找到的课程加入结果集
    for i in range(1, len(sorted_courses)):
        if sorted_courses[i]['start'] >= result[-1]['end']: # 选出下次课开始时间在上次课结束后的最早结束的课程，将其加入结果集中
            result.append(sorted_courses[i])
    return result


# 使用贪心算法获得集合覆盖问题的近似解
def set_cover_solution(complete_set: set, subsets: dict):
    final_result = list()
    while complete_set:                  # 集合还不空的情况下进入循环
        best_subset = None         # 保存交集最大的集合名
        covered_max = set()        # 交集最大的集合
        for set_name, subset in subsets.items():    # 找出各个子集与待覆盖的集合交集最大的集合
            covered = complete_set & subset
            if len(covered) > len(covered_max):
                covered_max = covered
                best_subset = set_name
        final_result.append(best_subset)       # 将集合名加入结果集中
        complete_set -= covered_max        # 计算差集并修正待覆盖的集合
    return final_result

